The present invention is directed toward a method for decoding information signals and, more particularly, toward a method for decoding information signals that have been error-correction coded in cyclic blocks and/or have been received through a medium that introduces Inter-Symbol Interference (ISI), such block-cyclic decoders generally referred to as tailbiting decoders.
FIG. 1 illustrates in path form a prior art Stack decoding method, implemented by a prior art Stack decoder, for decoding continuously convolutionally coded signals. The method is described for steady-state operation after the Stack decoder has been operating for a relatively long time in relation to any special start-up operations. At the instant depicted in FIG. 1, the Stack decoder has tested a number of possible sequences represented by paths moving from left to right one symbol, or node, at a time. Every time a path is extended by one symbol, all possible values of the new symbol have to be considered, resulting in a new fork. If the symbols are binary symbols, or bits, that can take on only one of two values, then the forks each have two times corresponding to the next binary symbol being either a xe2x80x9c1xe2x80x9d or a xe2x80x9c0xe2x80x9d. At each node just before a new fork is generated, a number of numerical quantities are stored in a memory (not shown) associated with the node. The quantities describe at least the path, or symbol history, by which the Stack decoder reached the node, and a cumulative probability value for that path.
For example, two probability values are depicted in FIG. 1, namely, a value P1 attached to a node 10 of highest probability, and a valve P2 attached to a node 12 of second highest probability. The description of the path can, for example, be a string of symbols representing which of the previous forks were taken to reach the current node plus the probability at the current node. Accordingly, at the node 10 the description may include the symbol string . . . 010101 and the probability value P1, while at the node 12 the description may include the symbol string . . . 00 and the probability value P2. Alternatively, the description can include the symbol corresponding to the last fork taken, plus a pointer to the preceding node at which that fork was taken. The latter is sometimes more memory-efficient as only one symbol need be stored at each node. If it is desired to reproduce the string of symbols along the path, a xe2x80x9ctrace-backxe2x80x9d operation may then be performed.
The prior art Stack algorithm shown in FIG. 1 proceeds by extending the path of highest probability by one symbol and re-evaluating the probabilities for the extended paths. The path is extended by creating two new branches (in the case of binary symbols) from the previous node 10 of highest probability (P1). The two new branches are represented by dashed lines in FIG. 1 and end in two new nodes 14 and 16 for which new probability values xP1 and yP1 are respectively calculated. The sum of the multipliers (x+y) does not equal unity because the particular path chosen to be extended may be incorrect. The result of a trial-extension of an erroneous path may thus provide further evidence that the erroneous path was incorrect, reducing the probability of the path from P1 to (x+y)P1. Multiplying this reduced path probability by the conditional branch probabilities x/(x+y) and y/(x+y), which do sum to unity, the probability for the two extended nodes xP1 and yP1 are obtained. The new probabilities xP1 and yP1 are then compared to the probabilities of other paths, particularly to the previous second highest probability P2, and to each other, to determine the node now having the highest probability which will be the next node extended to become two new nodes, and so forth.
Since multiplying the probability P1 by x and y, respectively, both of which must be less than unity, can only reduce the probability below P1, it often happens in the prior art Stack algorithm that the previously second highest probability P2 becomes the highest. When the node 12 having the probability P2 is extended instead of one of the new nodes 14 (xP1) or 16 (yP1), this is termed xe2x80x9cbacktrackingxe2x80x9d, as the relative probabilities provide a hint that the path passing through the node 10 (P1) may not have been the correct path, and that decoding should perhaps be resumed along a previously abandoned path. Noise is one of the factors which may lead a Stack decoder astray along an incorrect path.
It is a disadvantage of the prior art Stack algorithm that, under noisy conditions, much backtracking takes place with a consequent increase in processing. The prior art Stack algorithm suffers from the deficiency that backtracking to any previously abandoned node, however far back (e.g., 10, 50, 100 or even 1,000 bits), could in principle occur, leading to the amount of computation required to determine the best path being unbounded. Consequently there is a need for improved Stack algorithms that do not suffer to the same extent from this deficiency.
In the prior art, the Stack algorithm was envisaged for continuous decoding, such as continuous convolutional decoding. However, as has been mentioned in the prior art, for example in xe2x80x9cError Control Codingxe2x80x9d by Lin and Costello, (ISBN 0-13-283796-X), tail bits can be appended to a block of data prior to coding, the extra tail bits being transmitted so that the Stack decoder can end in a definitive end state. The use of tail bits adds additional redundancy and overhead to the transmission, causing the beginning and end bits to exhibit an improved error rate relative to bits in the middle of the transmission. This, however, may be of no utility since a lower error rate on all bits may be preferred, or alternatively, a transmission with lower overhead and therefore narrower bandwidth may also be preferred.
In a prior art decoding algorithm known as the Viterbi algorithm, the probability-indicating values are known as metrics. Because the Viterbi algorithm only compares probabilities for paths of the same length in symbols, indeterminate constants that add to, or multiply, the metrics do not affect the comparison, as they affect all paths alike. The Viterbi decoder can thus use simplified metrics which are the cumulative squared errors between hypothesized symbol coded values and received coded values. These simplified metrics are known as Euclidean distance metrics and are related to the logarithm of the reciprocal of the probability for the symbol sequence.
In the Stack algorithm, however, paths of different lengths must be compared, and the comparison is not then immune to additive terms that depend on the path length. Various methods are known to construct metrics for the Stack and similar algorithms that compare paths of different length. These metrics are generally Viterbi-type Euclidean-distance metrics modified by subtracting a value from the metric of a path every time the path is extended by one symbol. One such metric is known as the Fano metric which subtracts a value from the metric representative of the estimated mean square noise that is expected to be added per symbol extension, even to a correct path.
The present invention is directed toward overcoming one or more of the above-mentioned problems.
In a first embodiment of the present invention, a block of information symbols to be transmitted is generally regarded as a closed circle of information symbols. A coding algorithm is applied to the symbols lying in a segment of the circle to generate groups of coded symbols for each successive position of the segment, as the segment is moved around the circle one information symbol at a time. The groups of coded symbols are regarded as a closed circle of coded symbols corresponding to the closed circle of information symbols. The coded symbols are transmitted over a channel subject to error-inducing noise or other interference. This method of circular encoding is generally known as tailbiting.
A tailbiting, or Stack decoder according to the present invention receives the noisy signal and decodes it to reproduce the information symbol circle originally transmitted. The Stack decoder postulates information symbol sequences starting at any position around the circle, calculates likelihoods for the postulated symbol sequences by combining each sequence with corresponding soft-demodulated symbols, and extends the most probable sequence one symbol at a time until it either ceases to be the most probable sequence of those sequences tested, or until it extends completely around the circle. A sequence which successfully extends around the complete circle, and which remains the most probable sequence of those tested when the circle is complete, is the global optimum decoded sequence of the received signal. This is in contrast to prior art tailbiting Viterbi algorithms in which the most probable sequence among those sequences tested is not necessarily the global optimum.
In a second embodiment of the present invention, a coded or uncoded information symbol, or cyclic, block is modulated to form a transmitted signal block that is received at the decoder via a channel that introduces Inter-Symbol Interference (ISI). If desired, the inclusion of a short cyclic repeat of the transmitted signal by repeating a limited number of last-transmitted symbols of the block prior to the start of the transmitted signal block, or alternatively repeating a limited number of the first-transmitted symbols at the end of the block, or both, can force the ISI pattern to appear cyclic.
An inventive equalizing method for such signals includes postulating transmitted symbol sequences starting at any position within a cyclic block and calculating probabilities for the postulated sequences by combining the postulated symbols with the received signal. The most probable sequence is then extended successively by one symbol around the cyclic block until either it ceases to be the most probable sequence, or until the sequence extends completely around the cyclic block. A sequence which extends completely around the cyclic block while at the end still having the highest probability of all sequences tested is the global optimum equalization of the received signal. In this second embodiment of the invention, a tailbiting Viterbi equalizer may be used.
The inventive tailbiting Stack Algorithm used by the Stack decoder extends postulated sequences until the last symbol appended is the last symbol in the circle not previously postulated and adjacent to the first symbol postulated. There then remains a number Lxe2x88x921 of shifts of the decoding algorithm around the circle before it is once more in its starting position, where L corresponds to the constraint length of the encoder polynomials or the delay spread, in symbol periods, of a multipath channel. These Lxe2x88x921 final shifts are made to complete the likelihood calculation for the sequence and to use the remainder of the received signal samples, or soft-demodulated symbols, in the cycle that have not yet been processed. Once the last symbol in the circle is reached, the probability is updated L times in succession using previous values for the first Lxe2x88x921 symbols to obtain a xe2x80x9cfinalxe2x80x9d probability, or likelihood value, for the sequence. If the final probability value is still the highest probability value of all sequences tested, it is the global optimum decoded sequence and no other partial sequences need be extended. If not, the partial sequences having a higher probability are successively extended either until their probabilities fall below the already completed sequence of highest likelihood, or else until one of them becomes a complete circular sequence with a final probability that is greater than all other probabilities. Whenever a circular sequence is completed, all partial sequences having lower probabilities may be expunged to save memory, as they cannot be extended to obtain a higher probability (probabilities only decrease as the sequence is extended). The latter, desirable feature is not obtained in continuous, ie., non-circular, Stack decoders that do not ever reach a xe2x80x9cfinalxe2x80x9d probability.
The inventive Stack decoder may used to decode encoded and compressed digital speech data transmitted over a link subject to errors. Decoding may comprise decoding speech bits of lesser perceptual importance, and attempting to decode speech bits of high perceptual importance. When the Stack decoding algorithm for bits of higher perceptual importance fails to decode those bits within a given amount of time or given number of processor cycles, an erasure may be declared and passed to a speech decompressor which then uses previously correctly decoded speech data to construct an artificial fill-in waveform to mask the error event and thereby prevent unpleasant sounds, i.e., noise, interference, etc., from being heard by the listener.
Other aspects, objects and advantages of the present invention can be obtained from a study of the application, the drawings, and the appended claims.